The present invention relates to interpolation machines and more particularly to a high speed digital interpolation machine useful in converting from one color space to another.
One method to calculate the value of a complicated function is by table look up. For example, trigonometric functions such as sines and cosines are tabulated. If the value of the function is not tabulated at the desired point, then it can be approximated by a linear interpolation between the two closest tabulated points. For a 3-dimensional function, a 3-dimensional interpolation is required.
One useful application of 3-dimensional interpolation is conversion of color space variables. For example, color television images are broadcast in a luminance-chrominance color space, but a television receiver requires red, green, blue (RGB) color signals. The conversion from luminance- chrominance space to RGB can be done by three interpolations (one for the red signal, one for green and one for blue). In conventional color televison receivers, the conversion is done by analog means.
With the digital method described here a much more complex relationship between transmission and display primaries is possible. Consequently, a reduction in transmission bandwidth and an improvement in image quality can be achieved.
The invention also relates to graphic arts quality printing system, in which images must be color corrected prior to printing.
The invention also relates to multidimensional function synthesis. A function of 3 variables is tabulated at discrete values of the 3 range variables. The value of the function at non-tabulated points can be synthesized by interpolation.
Many digital techniques are known for performing interpolations. For a 3-dimensional color space, two types of interpolations are commonly used to approximate the continuous mapping function, namely, trilinear interpolation and 3-dimensional piecewise linear interpolation. For trilinear interpolation, a linear interpolation is done for each dimension of the color space. Let the range of the interpolating function be specified by the coordinates X, Y and Z. Let the value of the function, F, be tabulated at integer values of X, Y and Z. The trilinear interpolation function can be computed by the summation: ##EQU1##
This is the weighted sum form of trilinear interpolation. The interpolated value is a weighted sum of the values at the eight corner points of a cube in the XYZ space. Though the interpolation is linear in each dimension, trilinear inrterpolation fits a hyperbolic surface between the data points.
For piecewise linear interpolation, the model of the data space is of the form: EQU F(X,Y,Z)=a.sub.x X+a.sub.y y+a.sub.z Z+a.sub.0 ( 2)
It is necessary to determine the constants a.sub.x, a.sub.y, a.sub.z and a.sub.0 for all points in the space. Since there are four constants, a minimum of four samples of the function F are required. For 3-dimensional linear interpolation, the resulting cubes in the 3-dimensional space can be divided into five tetrahedrons per cube. The parameters of the linear equations are constant for each tetrahedron of the cube.
It is often desirable or necessary to transform color space data very rapidly. For example, for real-time updates of a 30 Hz color TV display from a 512.times.512 frame buffer, a new color point must be calculated approximately every 100 ns. For such high throughput rates, it is usually necessary to implement the color space transformation in hardware.
It is therefore a primary object of the present invention to provide transformation hardware which performs the interpolation very efficiently.
Yet another object of the invention is interpolation hardware which can update color television images in real time.
Still another object of the invention is interpolation hardware which is four to eight times faster than known digital interpolation techniques, or requires 1/4 to 1/8 the memory of other schemes.